# Definition for an Interval.
class Interval(object):
    def __init__(self, start=None, end=None):
        self.start = start
        self.end = end


class Solution(object):
    def employeeFreeTime(self, schedule):
        """
        :type schedule: [[Interval]]
        :rtype: [Interval]
        """
        n = len(schedule)
        start = []
        end = []
        for i in range(n):
            for j in range(len(schedule[i])):
                if j == 0:
                    start.append(-float('inf'))
                    end.append(schedule[i][j].start)
                else:
                    if j < len(schedule[i]):
                        start.append(schedule[i][j - 1].end)
                        end.append(schedule[i][j].start)
            start.append(schedule[i][-1].end)
            end.append(float('inf'))
        start.sort()
        end.sort()
        m = len(start)
        left_index = 0
        right_index = 0
        out = []
        while left_index < m and right_index < m:
            while start[left_index] >= end[right_index]:
                right_index += 1
            if left_index - right_index == n - 1:
                if start[left_index] != -float('inf') and end[right_index] != float('inf'):
                    out.append(Interval(start[left_index], end[right_index]))
            left_index += 1
        return out


